package week_seven;

import java.util.HashSet;
import java.util.Set;

public class NumberOfIslandsDisJointSet_200 {
    // private boolean[][] visit;
    private int m, n;
    int[] fa;

    int[] dx = {1, 0, -1, 0};
    int[] dy = {0, 1, 0, -1};

    public int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        // visit = new boolean[m][n];
        fa = new int[m * n];
        for (int i = 0; i < m * n; i++) fa[i] = i;

        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    for (int k = 0; k < 4; k++) {
                        int ni = i + dx[k];
                        int nj = j + dy[k];
                        if (ni < 0 || ni >= m || nj < 0 || nj >= n) continue;
                        if (grid[ni][nj] == '1') union(getIndex(ni, nj), getIndex(i, j));
                    }
                }
            }
        }

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    set.add(find(getIndex(i, j)));
                }
            }
        }

        return set.size();
    }

    private int getIndex(int i, int j) {
        return i * n + j;
    }

    private void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) fa[x] = y;
    }

    private int find(int x) {
        if (x == fa[x]) return x;
        return fa[x] = find(fa[x]);
    }
}
